#include <stdio.h>
#include <stdlib.h>
#include <strings.h>
#include <sys/socket.h>
#include <sys/types.h>
#include <netinet/in.h>
#include <errno.h>
#include <time.h>

// Verbose Output Enable
#define VERBOSE 1

// Time Output Enable
#define TIME 1

// Array Outup Enable
#define ARRAY 0


/* Function Definitions */

/* CREATE ARRAY *******************************************************************
*
*  Arguments: int size - size of the random array to be created
*
*  Return: unsined int* - sorted array created
*
***********************************************************************************/
unsigned int* createArray( int size );


/* MERGE ARRAY ********************************************************************
*
*  Arguments: unsigned int * buffer - first array to be merged
*	      unsigned int * buffer2 - second array to be merged
*	      int max - size of the final array
*
*  Return: unsined int* - sorted array created
*
***********************************************************************************/
unsigned int* mergeArray( unsigned int * buffer, unsigned int * buffer2, int max );


/* Main Program */

int main(int argc, char* argv[] ){

	/* Declarations */

	struct sockaddr_in control;
	struct sockaddr_in partner;
	struct sockaddr_in local;
	struct in_addr address;
	struct timespec time1;
	struct timespec time2;
	int lsock, asock, csock;
	unsigned int *buffer = NULL, *buffer2 = NULL, *final = NULL;
	int check, sum, max = 125;
	int size, i;
	struct in_addr message;
	int on = 1;
	errno = 0;

	// Invocation error handler
	if( argc != 2 ){
		printf( "Usage: node [CONTROL IP]\n" );
		return -1;
	}

	// LOCAL address setup
	bzero( &local, sizeof(local) );
	local.sin_family = AF_INET;
	local.sin_port = htons(20000);
	local.sin_addr.s_addr = INADDR_ANY;
	bzero( &(local.sin_zero), 8 );

	// Socket Declaration
	lsock = socket(AF_INET, SOCK_STREAM, 0 );
	if( lsock < 0 ){
		printf( "%s\n", (char *)strerror(errno) );
		printf( "EMERGENCY OVERRIDE: SOCKET CREATION ERROR\n" );
		return -1;
	}

	// Address Reuse Setup
	check = setsockopt(lsock, SOL_SOCKET, SO_REUSEADDR, &on, sizeof(on) );
	if( check < 0){
		printf( "%s\n", (char *)strerror(errno) );
		printf( "EMERGENCY OVERRIDE: SETOPT ERROR\n" );
		return -1;
	}

	// CONTROL address setup
	bzero( &control, sizeof(control) );
	control.sin_family = AF_INET;
	control.sin_port = htons(20000);
	inet_aton( argv[1], &address );
	control.sin_addr.s_addr = address.s_addr;
	bzero( &(control.sin_zero), 8 );

	// Bind LOCAL to lsock
	check = bind( lsock, (struct sockaddr *)&local, sizeof(struct sockaddr) );
	if( check < 0 ){
		printf( "%s\n", (char *)strerror(errno) );
		printf( "EMERGENCY OVERRIDE: BIND ERROR\n" );
		return -1;
	}

	// Listen to connections from PARTNERS
	check = listen( lsock, 5 );
	if( check < 0 ){
		printf("%s\n", (char *)strerror(errno) );
		printf( "EMERGENCY OVERRIDE: LISTEN ERROR\n" );
		return -1;
	}

	clock_gettime( CLOCK_THREAD_CPUTIME_ID, &time1 );

	// Initial array creation
	if(VERBOSE){ printf( "Creating 125 array...\n" ); }
	buffer =  createArray( max );
	if( buffer == NULL ){
		printf( "EMERGENCY OVERRIDE: CARRAY FATAL ERROR\n" );
		return -1;
	}

	// Elapsed Time Report
	clock_gettime( CLOCK_THREAD_CPUTIME_ID, &time2 );
	if(TIME){ printf( "Elapsed time[%s]: %d s %ld ns\n", (char *)inet_ntoa(local.sin_addr), (int)(time2.tv_sec-time1.tv_sec), time2.tv_nsec-time1.tv_nsec ); }

	if(ARRAY){
		printf( "125 Array: " );
		for( i = 0; i < 125; i++ ){
			printf( "%d ", buffer[i] );
		}
		printf( "\n" );
	}
	
	// Main Loop
	// max defines the size of the arrays being processed
	while( max < 1000 ){

		clock_gettime( CLOCK_THREAD_CPUTIME_ID, &time1 );

		// Socket declaration
		csock = socket(AF_INET, SOCK_STREAM, 0 );
		if( csock < 0 ){
			printf( "EMERGENCY OVERRIDE: CSOCKET CREATION ERROR\n" );
			return -1;
		}

		// Address Reuse Setup
		check = setsockopt( csock, SOL_SOCKET, SO_REUSEADDR, &on, sizeof(on) );
		if( check < 0 ){
			printf( "%s\n", (char *)strerror(errno) );
			printf( "EMERGENCY OVERRIDE: CSETOPT ERROR\n" );
			return -1;
		}
		
		// Connecting to CONTROL to acquire PARTNER
		if(VERBOSE){ printf( "Connecting to control...\n" ); }
		check = connect( csock, (struct sockaddr *)&control, sizeof(struct sockaddr) );
		if( check < 0 ){
			printf( "%s\n", (char *)strerror(errno) );
			printf( "EMERGENCY OVERRIDE: CONNECT ERROR\n" );
			return -1;
		}

		// Receive answer from CONTROL. If the message size is 0, then there is no PARTNER available, wait. 
		// If the message size isn't 0, the PARTNER address is at [message]
		sum = recv( csock, &message, sizeof(address), MSG_WAITALL );
		if( sum < 0 ){
			printf( "EMERGENCY OVERRIDE: RECEIVE ERROR\n");
			return -1;
		}

		// Close connection
		check = close( csock );
		if( check < 0 ){
			printf( "%s\n", (char *)strerror(errno) );
			printf( "EMERGENCY OVERRIDE: CLOSE ERROR\n" );
			return -1;
		}

		// Elapsed Time Report
		clock_gettime( CLOCK_THREAD_CPUTIME_ID, &time2 );
		if(TIME){ printf( "Elapsed time [%s]: %d s %ld ns\n", (char *)inet_ntoa(local.sin_addr), (int)(time2.tv_sec-time1.tv_sec), time2.tv_nsec-time1.tv_nsec ); }

		// If there is a PARTNER available
		if( sum != 0){

			clock_gettime( CLOCK_THREAD_CPUTIME_ID, &time1 );
		
			if(VERBOSE){ printf( "Received partner: %s\n", (char *)inet_ntoa(message) ); }

			// PARTNER address setup
			address = message;
			bzero( &partner, sizeof(partner) );
			partner.sin_family = AF_INET;
			partner.sin_port = htons(20000);
			partner.sin_addr.s_addr = address.s_addr;
			bzero( &(partner.sin_zero), 8 );
		
			// Socket Creation
			csock = socket( AF_INET, SOCK_STREAM, 0 );
			if( csock < 0 ){
				printf( "EMERGENCY OVERRIDE: PARTNER SOCKET ERROR\n" );
				return -1;
			}
			
			// Address Reuse Setup
			check = setsockopt( csock, SOL_SOCKET, SO_REUSEADDR, &on, sizeof(on) );
			if( check < 0 ){
				printf( "EMERGENCY OVERRIDE: PARTNER SETOPT ERROR\n" );
				return -1;					
			}

			// Connect to the PARTNER assigned
			if(VERBOSE){ printf( "Conneting to %s\n", (char *)inet_ntoa(partner.sin_addr) ); }
			check = connect( csock, (struct sockaddr *)&partner, sizeof(struct sockaddr));
			if( check < 0 ){
				printf( "%s\n", (char *)strerror(errno) );
				printf( "EMERGENCY OVERRIDE: PARTNER CONNECT ERROR\n");
				return -1;
			}
	
			// Send Array to the PARTNER
			check = send( csock, buffer, sizeof(unsigned int)*max, 0 );
			if( check < 0 ){
				printf( "EMERGENCY OVERRIDE: PARTNER SEND ERROR\n" );
				return -1;
			}
			
			// Close Connection
			check = close( csock );
			if( check < 0 ){
				printf( "EMERGENCY OVERRIDE: PARTNER CSOCKET CLOSE ERROR\n" );
				return -1;
			}
			
			// Elapsed Time Report
			clock_gettime( CLOCK_THREAD_CPUTIME_ID, &time2 );
			if(TIME){ printf( "Elapsed time [%s]: %d s %ld ns\n", (char *)inet_ntoa(local.sin_addr), (int)(time2.tv_sec-time1.tv_sec), time2.tv_nsec-time1.tv_nsec ); }

			// Exit Main Loop
			// max = 2000 defines if the program is or isn't the final node
			max = 2000;

		// If there is no PARTNER available
		} else {

			clock_gettime( CLOCK_THREAD_CPUTIME_ID, &time1 );

			// Wait a Foreign Connection
			if(VERBOSE){ printf( "Waiting Connections...\n" ); }
			size = sizeof(struct sockaddr);
			asock = accept( lsock, (struct sockaddr *)&partner, &size );
			if( asock < 0 ){
				printf( "EMERGENCY OVERRIDE: ACCEPT ERROR\n" );
				return -1;
			}
			
			// When a PARTNER connects, receive the Array from him
			if(VERBOSE){ printf( "Conection from %s\n", (char *)inet_ntoa(partner.sin_addr) ); }
			buffer2 = malloc( sizeof(unsigned int)*max );
			check = recv( asock, buffer2, sizeof(unsigned int)*max, MSG_WAITALL );
			if( check < 0 ){
				printf( "%s\n", (char *)strerror(errno) );
				printf( "EMERGENCY OVERRIDE: PARTNER RECEIVE ERROR\n" );
				return -1;
			}

			if(ARRAY){
				printf( "Received array: " );
				for( i = 0; i < max; i++ ){
					printf( "%d ", buffer2[i] );
				}
				printf( "\n" );
			}

			// Elapsed Time report
			clock_gettime( CLOCK_THREAD_CPUTIME_ID, &time2 );
			if(TIME){ printf( "Elapsed time [%s]: %d s %ld ns\n", (char *)inet_ntoa(local.sin_addr), (int)(time2.tv_sec-time1.tv_sec), time2.tv_nsec-time1.tv_nsec ); }

			clock_gettime( CLOCK_THREAD_CPUTIME_ID, &time1 );

			// Merge local Array and the received Array
			if(VERBOSE){ printf( "Merging arrays...\n" ); }
			max = 2 * max;
			buffer = mergeArray( buffer, buffer2, max );
			if( buffer == NULL ){
				printf( "EMERGENCY OVERRIDE: MARRAY ERROR\n");
				return -1;
			}

			clock_gettime( CLOCK_THREAD_CPUTIME_ID, &time2 );

			// Free unused buffer
			if( buffer2 != NULL ){
				free(buffer2);
			}

			if(ARRAY){
				printf( "Merged Array: " );
				for( i = 0; i < max; i++ ){
					printf( "%d ", buffer[i] );
				}
				printf( "\n" );
			}

			// Elapsed Time Report
			if(TIME){ printf( "Elapsed time [%s]: %d s %ld ns\n", (char *)inet_ntoa(local.sin_addr), (int)(time2.tv_sec-time1.tv_sec), time2.tv_nsec-time1.tv_nsec ); }

			check = close( asock );
			if( check < 0 ){
				printf( "EMERGENCY OVERRIDE: ASOCK CLOSE ERROR\n" );
				return -1;
			}
					
			//Main Loop End
		}
	}

	// If the program isn't the final node
	if( max == 2000 ){

		clock_gettime( CLOCK_THREAD_CPUTIME_ID, &time1 );

		// Wait for the connection from CONTROL
		if(VERBOSE){ printf( "Waiting for final contact...\n" ); }
		asock = accept( lsock, (struct sockaddr *)&partner, &size );
		if( asock < 0 ){
			printf( "EMERGENCY OVERRIDE: FINAL ACCEPT ERROR" );
		}
		
		// Receive the final sorted array 
		final = malloc( sizeof(unsigned int)*1000 );
		check = recv( asock, final, sizeof(unsigned int)*1000, MSG_WAITALL );
		if( check < 0 ){
			printf( "EMERGENCY OVERRIDE: FINAL RECEIVE ERROR\n" );
			return -1;
		}
		
		// Print results
		if(VERBOSE){
			printf( "FINAL ARRAY:\n" );
			for( i = 0; i < 1000; i++ ){
				printf( "%u ", final[i] );
			}
			printf("\n");
		}

		// Elapsed Time report
		clock_gettime( CLOCK_THREAD_CPUTIME_ID, &time2 );
		if(TIME){ printf( "Elapsed time [%s]: %d s %ld ns\n", (char *)inet_ntoa(local.sin_addr), (int)(time2.tv_sec-time1.tv_sec), time2.tv_nsec-time1.tv_nsec ); }

	// If the program is the final node
	} else {

		clock_gettime( CLOCK_THREAD_CPUTIME_ID, &time1 );

		// Connect to the CONTROL to submit final array
		if(VERBOSE){ printf("Sending final array...\n" ); }
		csock = socket( AF_INET, SOCK_STREAM, 0 );
		if( csock < 0 ){
			printf( "EMERGENCY OVERRIDE: PARTNER SOCKET ERROR\n" );
			return -1;
		}

		check = setsockopt( csock, SOL_SOCKET, SO_REUSEADDR, &on, sizeof(on) );
		if( check < 0 ){
			printf( "EMERGENCY OVERRIDE: PARTNER SETOPT ERROR\n" );
			return -1;					
		}

		// Connect to CONTROL
		check = connect( csock, (struct sockaddr *)&control, sizeof(struct sockaddr) );
		if( check < 0 ){
			printf( "EMERGENCY OVERRIDE: FINAL CONNECT ERROR\n" );
			return -1;
		}

		// Send final array
		check = send( csock, buffer, sizeof(unsigned int)*1000, 0 );
		if( check < 0 ){
			printf( "EMERGENCY OVERRIDE: FINAL SEND ERROR\n" );
			return -1;
		}

		// Print results
		if(ARRAY){
			printf( "FINAL ARRAY:\n" );
			for( i = 0; i < 1000; i++ ){
				printf( "%u ", buffer[i] );
			}
			printf( "\n" );
		}

		// Elapsed time report
		clock_gettime( CLOCK_THREAD_CPUTIME_ID, &time2 );
		if(TIME){ printf( "Elapsed time [%s]: %d s %ld ns\n", (char *)inet_ntoa(local.sin_addr), (int)(time2.tv_sec-time1.tv_sec), time2.tv_nsec-time1.tv_nsec ); }
	}


	free(final);
	free(buffer);
	close(csock);
	close(asock);
	close(lsock);

	// Final Elapsed Time Report
	clock_gettime( CLOCK_THREAD_CPUTIME_ID, &time1 );
	if(TIME){ printf( "Total Elapsed time [%s]: %d s %ld ns\n", (char *)inet_ntoa(local.sin_addr), (int)time1.tv_sec, time1.tv_nsec ); }

	return 0;
}

unsigned int* createArray( int size ){

	FILE* rand;
	unsigned int swap;
	unsigned int* buffer;
	int i, check;
	int max;
	int n = 1;

	max = size;
	
	// Memory Allocation
	buffer = malloc( sizeof(unsigned int)*max );
	if( buffer == NULL ){
		printf( "CARRAY: MALLOC BUFFER NULL\n" );
		return NULL;
	}

	// Read Random Numbers from urandom 
	rand = fopen("/dev/urandom", "r" );
	if( rand ==  NULL ){
		printf( "CARRAY: RAND OPEN NULL\n" );
		return NULL;
	}

	// Write Numbers to Array
	for( i = 0; i < max; i++ ){
		
		check = fread( &(buffer[i]), sizeof(unsigned int), 1, rand );
		if( check == -1 ){
			printf( "CARRAY: READ RAND ERROR\n" );
			return NULL;
		}
		// Limits the Numbers between 0 and 999
		buffer[i] = buffer[i]%1000;
	}
	fclose(rand);

	// HeapSort
	while( max > 1 ){

		for( i = 1; i < max; i++ ){
	
			while( (((i+1)/n)-1 != 0) && (buffer[(((i+1)/n)-1)] > buffer[(((i+1)/(2*n))-1)]) ){

				swap = buffer[(((i+1)/(2*n))-1)];
				buffer[(((i+1)/(2*n))-1)] = buffer[(((i+1)/n)-1)];
				buffer[(((i+1)/n)-1)] = swap;
				n = 2*n;
			}
			n = 1; 

		}
	
		swap = buffer[max-1];
		buffer[max-1] = buffer[0];
		buffer[0] = swap;
		max--;
	}

	return buffer;
}

unsigned int * mergeArray( unsigned int * buffer, unsigned int * buffer2, int max ){
	
	int i, n = 1;
	unsigned int swap;

	// Extends the size of buffer to concatenate
	buffer = realloc( buffer, sizeof(unsigned int)*max );
	if( buffer == NULL ){
		printf("MA: REALLOC ERROR\n" );
		return NULL;
	}

	// Copy one buffer to the resized one
	for( i = max/2; i < max ; i++ ){
		buffer[i] = buffer2[ i%(max/2) ];
	}	

	//heapsort
	while( max > 1 ){

		for( i = 1; i < max; i++ ){
	
			while( (((i+1)/n)-1 != 0) && (buffer[(((i+1)/n)-1)] > buffer[(((i+1)/(2*n))-1)]) ){

				swap = buffer[(((i+1)/(2*n))-1)];
				buffer[(((i+1)/(2*n))-1)] = buffer[(((i+1)/n)-1)];
				buffer[(((i+1)/n)-1)] = swap;
				n = 2*n;
			}
			n = 1; 

		}
	
		swap = buffer[max-1];
		buffer[max-1] = buffer[0];
		buffer[0] = swap;
		max--;
	}

	return buffer;
}
